
<html><head>
<title>flibs/backtracking - flibs</title>
<style type="text/css"><!--
    HTML {
	background: 	#FFFFFF;
	color: 		black;
    }
    BODY {
	background: 	#FFFFFF;
	color:	 	black;
    }
    DIV.doctools {
	margin-left:	10%;
	margin-right:	10%;
    }
    DIV.doctools H1,DIV.doctools H2 {
	margin-left:	-5%;
    }
    H1, H2, H3, H4 {
	margin-top: 	1em;
	font-family:	sans-serif;
	font-size:	large;
	color:		#005A9C;
	background: 	transparent;
	text-align:		left;
    }
    H1.title {
	text-align: center;
    }
    UL,OL {
	margin-right: 0em;
	margin-top: 3pt;
	margin-bottom: 3pt;
    }
    UL LI {
	list-style: disc;
    }
    OL LI {
	list-style: decimal;
    }
    DT {
	padding-top: 	1ex;
    }
    UL.toc,UL.toc UL, UL.toc UL UL {
	font:		normal 12pt/14pt sans-serif;
	list-style:	none;
    }
    LI.section, LI.subsection {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding: 	0em;
    }
    PRE {
	display: 	block;
	font-family:	monospace;
	white-space:	pre;
	margin:		0%;
	padding-top:	0.5ex;
	padding-bottom:	0.5ex;
	padding-left:	1ex;
	padding-right:	1ex;
	width:		100%;
    }
    PRE.example {
	color: 		black;
	background: 	#f5dcb3;
	border:		1px solid black;
    }
    UL.requirements LI, UL.syntax LI {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding:	0em;
    }
    DIV.synopsis {
	color: 		black;
	background: 	#80ffff;
	border:		1px solid black;
	font-family:	serif;
	margin-top: 	1em;
	margin-bottom: 	1em;
    }
    UL.syntax {
	margin-top: 	1em;
	border-top:	1px solid black;
    }
    UL.requirements {
	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<! -- Generated from file 'computing/backtrack.man' by tcllib/doctools with format 'html'
   -->
<! -- Copyright &copy; 2006 Arjen Markus &lt;arjenmarkus@sourceforge.net&gt;
   -->
<! -- CVS: $Id: backtrack.html,v 1.2 2013/05/13 08:03:15 knystrom Exp $ flibs/backtracking.n
   -->
<body><div class="doctools">
<h1 class="title">flibs/backtracking(n) 1.1  &quot;flibs&quot;</h1>
<div id="name" class="section"><h2><a name="name">Name</a></h2>
<p>flibs/backtracking - Backtracking</p>
</div>
<div id="toc" class="section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="toc">
<li class="section"><a href="#toc">Table Of Contents</a></li>
<li class="section"><a href="#synopsis">Synopsis</a></li>
<li class="section"><a href="#section1">Description</a></li>
<li class="section"><a href="#section2">ROUTINES</a></li>
<li class="section"><a href="#section3">TODO</a></li>
<li class="section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="synopsis">
<ul class="syntax">
<li><a href="#1"><b class="cmd">call runtests( testproc )</b></a></li>
<li><a href="#2"><b class="cmd">call test( proc, text )</b></a></li>
<li><a href="#3"><b class="cmd">call assert_true( cond, text )</b></a></li>
<li><a href="#4"><b class="cmd">exists = funit_file_exists( filename )</b></a></li>
<li><a href="#5"><b class="cmd">call funit_get_lun( lun )</b></a></li>
<li><a href="#6"><b class="cmd">call funit_remove_file( filename )</b></a></li>
<li><a href="#7"><b class="cmd">call funit_make_empty_file( filename )</b></a></li>
</ul>
</div>
</div>
<div id="section1" class="section"><h2><a name="section1">Description</a></h2>
<p>The module <em>Backtracking</em> implements in a general way a well-known
algorithm to solve certain combinatorial problems. The module actually
consists of a single routine that forms the framework of the algorithm
and is to be used in conjunction with a small set of user-defined
routines that implement the specific problem.</p>
<p>The backtracking technique is especially useful if you can build a
solution in stages. The classic example is the &quot;eight queens&quot; problem,
where you must place eight queens on a chess board in such a way that
none can get another in one move. A little thought shows that
each queen must be placed in its own column (or row). Placing the first
queen in the first column gives us eight possibilities. Placing the
second is only possible if it is not within the range of the first one.</p>
<p>If it is, it makes no sense to continue so we can eliminate in the
second step a whole subset of possible configurations, namely those with
the second queeen within range of the first.
We can continue building up a partial solution in this way until we
finally have eight queens on the board.</p>
<p>The idea of the module is that all the data that describe a possible
partial solution to the problem are contained in a derived type called
SOLUTION_DATA. Then the user-defined routine <em>generate</em> generates
a new set of partial solutions based on this.</p>
<p>The new set is examined to see if any is acceptable within the context
of the problem, which is done via another user-defined routine.</p>
<p>Each acceptable solution within this new step may give rise to its own
set of further solutions. This way the partial solutions are extended in
each step until finally a complete solution is found.</p>
</div>
<div id="section2" class="section"><h2><a name="section2">ROUTINES</a></h2>
<p>The module backtracking contains</p>
<dl class="definitions">
<dt><a name="1"><b class="cmd">call runtests( testproc )</b></a></dt>
<dd><p>Routine to start the unit tests. It checks if the file &quot;funit.run&quot;
exists. If so, it will call the subroutine <em>testproc</em> that was
passed. Otherwise it will simply return, so that the ordinary program
execution may continue.</p>
<p>If the subroutine testproc returns, the program stops.</p>
<dl class="arguments">
<dt>subroutine <i class="arg">testproc</i></dt>
<dd><p>Subroutine that calls the individual test routines. It takes no
arguments. It wil generally exist of a series of calls to the
routine <em>test</em> - see below.</p></dd>
</dl></dd>
<dt><a name="2"><b class="cmd">call test( proc, text )</b></a></dt>
<dd><p>Routine to run the individual unit test routine (emph proc). It decides
if the test has not run yet and if so, the test routine is called.
Otherwise it is skipped.</p>
<p><em>test</em> takes care of all administrative details.</p>
<p>Note: to make it possible to use <em>private</em> unit test routines,
the source code of this subroutine is kept in a separate file,
<em>funit_test.f90</em> that should be included in an appropriate
place in the program's sources. This way, you can make it a private
routine in each module. The only public access to the unit testing
routines is then via the subroutine <em>testproc</em> that is passed to
<em>runtests</em>.</p>
<dl class="arguments">
<dt>subroutine <i class="arg">proc</i></dt>
<dd><p>Subroutine that implements an individual unit test. It takes no
arguments. Within each such subroutine the complete unit test is run.</p></dd>
<dt>character(len=*), intent(in) <i class="arg">text</i></dt>
<dd><p>Text describing the particular unit test. It is printed in the log
file.</p></dd>
</dl></dd>
<dt><a name="3"><b class="cmd">call assert_true( cond, text )</b></a></dt>
<dd><p>Routine to check that a condition is true. If not, a message is printed
in the log file and the number of failures is increased.</p>
<dl class="arguments">
<dt>logical <i class="arg">cond</i></dt>
<dd><p>The condition to be checked</p></dd>
<dt>character(len=*), intent(in) <i class="arg">text</i></dt>
<dd><p>Text describing the condition</p></dd>
</dl></dd>
<dt><a name="4"><b class="cmd">exists = funit_file_exists( filename )</b></a></dt>
<dd><p>Logical function to check that a particular file exists</p>
<dl class="arguments">
<dt>character(len=*), intent(in) <i class="arg">filename</i></dt>
<dd><p>Name of the file to be checked</p></dd>
</dl></dd>
<dt><a name="5"><b class="cmd">call funit_get_lun( lun )</b></a></dt>
<dd><p>Subroutine to get a free LU-number</p>
<dl class="arguments">
<dt>integer, intent(out) <i class="arg">lun</i></dt>
<dd><p>Next free LU-number</p></dd>
</dl></dd>
<dt><a name="6"><b class="cmd">call funit_remove_file( filename )</b></a></dt>
<dd><p>Subroutine to remove (delete) a file</p>
<dl class="arguments">
<dt>character(len=*), intent(in) <i class="arg">filename</i></dt>
<dd><p>Name of the file to be removed</p></dd>
</dl></dd>
<dt><a name="7"><b class="cmd">call funit_make_empty_file( filename )</b></a></dt>
<dd><p>Subroutine to make a new, empty file</p>
<dl class="arguments">
<dt>character(len=*), intent(in) <i class="arg">filename</i></dt>
<dd><p>Name of the file to be created</p></dd>
</dl></dd>
</dl>
</div>
<div id="section3" class="section"><h2><a name="section3">TODO</a></h2>
<p>The following things are still left to do:</p>
<ul class="itemized">
<li><p>Proper inclusion of the routine <em>prolog</em> and <em>epilog</em></p></li>
<li><p>Extension of the set of assertion routines</p></li>
</ul>
</div>
<div id="copyright" class="section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2006 Arjen Markus &lt;arjenmarkus@sourceforge.net&gt;</p>
</div>
</div></body></html>